package apii.algorithm.fingerprints;

import java.util.*;

/**
 * <b>Note:</b> thread safe.
 * <p>
 * <b> Note:</b> Doesn't create threads.
 * <p>
 * This is queue implementation that supports additional minimum over all
 * elements operation. For more information see <a
 * href="http://e-maxx.ru/algo/stacks_for_minima">e-maxx</a>.
 * 
 * @author Alex
 * 
 * @param <T>
 */
public class MinQueue<T extends Comparable<? super T>> {
	private int n1;
	private Object[] hash1;
	private int min1;
	private int n2;
	private Object[] hash2;
	private int[] min2;

	public MinQueue(int size) {
		hash1 = new Object[size];
		hash2 = new Object[size];
		min2 = new int[size];
	}

	@SuppressWarnings("unchecked")
	public void push(T hash) {
		if (hash == null)
			throw new IllegalArgumentException();
		if (n1 + n2 == hash1.length)
			throw new IllegalStateException();
		hash1[n1++] = hash;
		if (n1 == 1 || hash.compareTo((T) hash1[min1]) <= 0)
			min1 = n1 - 1;
	}

	@SuppressWarnings("unchecked")
	public void pop() {
		if (n1 == 0 && n2 == 0)
			throw new IllegalStateException();
		if (n2 == 0) {
			while (n1 > 0) {
				--n1;
				hash2[n2] = hash1[n1];
				min2[n2] = n2 == 0
						|| ((T) hash2[n2]).compareTo((T) hash2[min2[n2 - 1]]) < 0 ? n2
						: min2[n2 - 1];
				++n2;
			}
		}
		--n2;
	}

	@SuppressWarnings("unchecked")
	public T getMin() {
		if (n1 == 0 && n2 == 0)
			throw new IllegalStateException();
		return (T) (firstMin() ? hash1[min1] : hash2[min2[n2 - 1]]);
	}

	public int getMinPos() {
		if (n1 == 0 && n2 == 0)
			throw new IllegalStateException();
		return firstMin() ? n2 + min1 : n2 - 1 - min2[n2 - 1];
	}

	@SuppressWarnings("unchecked")
	private boolean firstMin() {
		return n1 != 0
				&& (n2 == 0 || ((T) hash1[min1])
						.compareTo((T) (hash2[min2[n2 - 1]])) <= 0);
	}
}